1. Field of the Invention
The present invention relates to a COordinate Rotational DIgital Computer (CORDIC) method and a CORDIC architecture applied in vector rotation, and more particularly, to a CORDIC method based on Extended Elementary-Angle Sets (EEAS) and Trellis-based Searching (TBS) and its architecture.
2. Description of Related Art
Currently, vector rotation is the kernel of various digital signal-processing applications, including discrete orthogonal transformations, lattice-based digital filtering, matrix computation, complex-valued number manipulation, etc. In X-Y coordinates one vector rotation operation can be expressed as:
      [                                        x            out                                                            y            out                                ]    =            [                                                  cos              ⁢                                                          ⁢              θ                                                                          -                sin                            ⁢                                                          ⁢              θ                                                                          sin              ⁢                                                          ⁢              θ                                                          cos              ⁢                                                          ⁢              θ                                          ]        ·          [                                                  x              in                                                                          y              in                                          ]      
FIG. 1 shows hardware architecture used to implement the vector rotation operation, which requires two adders 11 and four multipliers 12. That is, the execution of one vector rotation operation will require executing two addition operations and four multiplication operations. The complexity of such an execution is too high. Reducing the wordlength can decrease the complexity. However, the SQNR will be increased accordingly.
The CORDIC algorithm is a well-known iterative method for the computation of vector rotation, which requires only one shift operation and one addition operation to perform a vector rotation operation. The CORDIC algorithm decomposes the rotation angle θ into a combination of pre-defined elementary angles as follows:
                              θ          =                                                    ∑                                  i                  =                  0                                                  N                  -                  1                                            ⁢                                                μ                  ⁡                                      (                    i                    )                                                  ⁢                                  a                  ⁡                                      (                    i                    )                                                                        +            ɛ                          ,                            (        1        )            where N is the number of elementary angles, μ={1, −1} is the rotation sequence which determines the direction of the i-th elementary angle of a(i)=tan−1(2−i), and ε denotes the residue angle.
Based on equation (1), the recurrence equations of the CORDIC algorithm can be written as
                    {                                                                                                  x                    ⁡                                          (                                              i                        +                        1                                            )                                                        =                                                            x                      ⁡                                              (                        i                        )                                                              -                                                                  μ                        ⁡                                                  (                          i                          )                                                                    ⁢                                              y                        ⁡                                                  (                          i                          )                                                                    ⁢                                              2                                                  -                          i                                                                                                                                                                                                              y                    ⁡                                          (                                              i                        +                        1                                            )                                                        =                                                            y                      ⁡                                              (                        i                        )                                                              +                                                                  μ                        ⁡                                                  (                          i                          )                                                                    ⁢                                              x                        ⁡                                                  (                          i                          )                                                                    ⁢                                              2                                                  -                          i                                                                                                                                                  ,                                    (        2        )            for i=0, 1, . . . , N−1. In practical fixed-point implementation, for data wordlength of W bits, no more than W iterations of the recurrence relation in equation (2) need be performed, i.e., N≦W. Also, the final values, x(N) and y(N), need to be scaled by an accumulated scaling factor expressed as follows:
                    P        =                                            (                                                ∏                                      i                    =                    0                                                        N                    -                    1                                                  ⁢                                                      1                    +                                          2                                                                        -                          2                                                ⁢                        i                                                                                                        )                                      -              1                                .                                    (        3        )            
In the above CORDIC algorithm, each elementary angle needs to be performed sequentially so as to complete the micro-rotation phase. However, in the applications where the rotation angles are known in advance, it would be advantageous to relax the sequential constraint on the micro-rotation phase. The angle recoding (AR) technique is done by extending the set of μ(i) from {1, −1} to {1, −1, 0}. By substituting μ(i)=0 into equation (2), one can skip the micro-rotation of the elementary angle a(i )=tan−1(2−i). Nevertheless, the AR technique imposes no restriction on the iteration number. Rotation angles of different values may need unequal numbers of iterations, which may lead to bus/timing alignment problems in VLSI circuits. Therefore, it is desired for the above CORDIC algorithm to be improved to mitigate and/or obviate the aforementioned problems.